package DynamicProgrammingPackage;

public class findMaxForm_ {


    // 1. dp[i][j] 表示 容量为i个0,j个1的背包可以装dp[i][j]个物品
    // 2. 递推公式: dp[i][j] = Math.max(dp[i][j],dp[i - x][j - y] + 1)
    // 3. 初始化 dp[*] = 0; 需要防止初值覆盖
    // 4. 遍历顺序: 先遍历物品 后遍历背包 背包从后向前遍历
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int x = 0;
            int y = 0;
            char[] charArray = str.toCharArray();
            for (char c : charArray) {
                if (c == '0') x += 1;
                if (c == '1') y += 1;
            }
            for (int i = m ; i >= x ; i--) {
                for (int j = n ; j >= y ; j--) {
                    dp[i][j] = Math.max(dp[i - x][j - y] + 1, dp[i][j]);
                }
            }
        }
        return dp[m][n];
    }
}
